# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 19/50 最长递增子序列
# leetcode第300题: https://leetcode.cn/problems/longest-increasing-subsequence/description/
# Date: 2024/11/6
import bisect
from typing import Callable

from leetcode import test


def lengthOfLIS_dp(nums: list[int]) -> int:
    """使用动态规划来实现, 其中dp[i]为以第i个数字为结尾的最长子序列的长度
    例如 nums = [10, 9, 2, 5, 3, 7, 101, 18]。
          dp  =  [1, 1, 1, 2, 2, 3, 4, 4]
    """
    n = len(nums)
    if n < 2:
        return 1

    dp = [0] * n
    res = 0

    for i in range(n):
        dp[i] = 1
        max_len = 1
        for j in range(i - 1, -1, -1):
            if nums[i] > nums[j]:
                max_len = max(max_len, dp[j] + 1)
        dp[i] = max_len
        res = max(res, max_len)
    return res


def lengthOfLIS_bis(nums: list[int]) -> int:
    """使用二分查找的方法
    例如 nums = [10, 9, 2, 5, 3, 7, 101, 18]。
    tails数组，用于保存当前的最长递增子序列的最后一个元素
    num = 10：tails 为空，那么pos=0, 则将 10 添加到 tails。tails = [10]
    num = 9：9 小于 10，替换掉 tails[0]，更新为 tails = [9]
    num = 2：2 小于 9，替换掉 tails[0]，更新为 tails = [2]
    num = 5：5 大于 2，将 5 添加到 tails，更新为 tails = [2, 5]
    num = 3：3 小于 5，替换 tails[1]，更新为 tails = [2, 3]
    num = 7：7 大于 3，将 7 添加到 tails，更新为 tails = [2, 3, 7]
    num = 101：101 大于 7，将 101 添加到 tails，更新为 tails = [2, 3, 7, 101]
    num = 18：18 小于 101，替换 tails[3]，更新为 tails = [2, 3, 7, 18]
    最终 tails 的长度是 4，即最长递增子序列的长度。
    """
    tails = []

    def bisect_in(a: list[int], x: int) -> int:
        """
        二分查找返回插入数字x应该在有序数组a中插入的位置
        :param a: 一个排序的数组
        :param x: 需要插入的对象
        :return: x应该在插入数组中的位置
        """
        left, right = 0, len(a)
        while left < right:
            mid = (left + right) // 2
            if a[mid] < x:
                left = mid + 1
            else:
                right = mid
        return left

    for num in nums:
        """bisect_left() 返回的是元素应该插入的位置，以保持列表的升序排列。如果元素已经存在于列表中，它返回的是元素第一次出现的位置。
        这里使用二分查找找到 num 在 tails 中的位置
        """
        # pos = bisect.bisect_left(tails, num)
        pos = bisect_in(tails, num)

        # 如果 num 大于 tails 中的所有元素，则添加到末尾
        if pos == len(tails):
            tails.append(num)
        else:
            # 否则，替换掉 tails 中第一个大于等于 num 的元素
            tails[pos] = num

    # tails 数组的长度即为最长递增子序列的长度
    return len(tails)


if __name__ == '__main__':
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    nums1 = [0, 1, 0, 3, 2, 3]
    nums2 = [7, 7, 7, 7, 7, 7, 7]
    nums3 = [1, 3, 6, 7, 9, 4, 10, 5, 6]
    inp = [{"nums": nums}, {"nums": nums1}, {"nums": nums2}, {"nums": nums3}, ]
    out = [4, 4, 1, 6]
    test.test_function(lengthOfLIS_dp, inp, out)
    test.test_function(lengthOfLIS_bis, inp, out)
